/********************DIJKSTRA'S ALGOTITHM********************************/

import java.util.*;
class Graph
{
int g[][];
int v,e;
int d[],p[],visited[];

void creategraph()
{
	int a,b,w;
	Scanner kbd=new Scanner(System.in);
	System.out.println("Enter numbher of vertices");
	v=kbd.nextInt();
	System.out.println("Enter number of edges");
	e=kbd.nextInt();
	g=new int[v+1][v+1];
	
	for(int i=1;i<=v;i++)
	for(int j=1;j<=v;j++)
	g[i][j]=0;
	for(int i=1;i<=e;i++)
	{
		System.out.println("enter edge information");
		a=kbd.nextInt();
		b=kbd.nextInt();
		System.out.println("enter weight of this egde");
		w=kbd.nextInt();
		g[a][b]=g[b][a]=w;
	}
}

void calldij()
{
	visited=new int[v+1];
	d=new int[v+1];
	p= new int[v+1];
	for(int i=1;i<=v;i++)
		p[i]=visited[i]=0;
	for(int i=1;i<=v;i++)
		d[i]=32767;
	dij();
}

void dij()
{
	int c,current,mincost=0,source,dest;
	System.out.println("Enetr source n destination vertex");
	Scanner kbd=new Scanner(System.in);
	
	source=kbd.nextInt();
	dest=kbd.nextInt();

 	current=source;
	visited[current]=1;
	d[current]=0;
	while(current!=dest)
	{
		int dc=d[current];
		for(int i=1;i<=v;i++)
		{
			if(g[current][i]!=0 && visited[i]!=1)
			if(g[current][i]+dc < d[i])
			{
				d[i]=g[current][i] + dc;
				p[i]=current;
			}
		}

		int min=32767;
		for(int i=1;i<=v;i++)
		{	
			if(visited[i]!=1 && d[i]<min)
			{
				min=d[i];
				current=i;
			}
		}
		visited[current]=1;
	}
	System.out.println("Shortest distance=" +d[dest]);
}
}

public class Dij
{
	public static void main(String args[])
	{
		Graph g=new Graph();
		g.creategraph();
		g.calldij();
	}
}

/*************************************OUTPUT**************************************

C:\Program Files\Java\jdk1.6.0_04\bin>javac Dij.java

C:\Program Files\Java\jdk1.6.0_04\bin>java Dij
Enter numbher of vertices
4
Enter number of edges
6
enter edge information
1 2
enter weight of this egde
1
enter edge information
1 3
enter weight of this egde
2
enter edge information
2 4
enter weight of this egde
5
enter edge information
3 4
enter weight of this egde
6
enter edge information
1 4
enter weight of this egde
4
enter edge information
3 2
enter weight of this egde
3
Enetr source n destination vertex
1 4
Shortest distance=4
*/